package code.commonAlgorithm;

/**
 * @author 26029
 * @date 2025/4/16
 * @description
 */
public class InsertSort {
    // 插入排序主函数
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int current = arr[i]; // 当前要插入的元素
            int j = i - 1;

            // 将前面比 current 大的元素往后挪
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j]; // 往后移
                j--;
            }

            // 找到了合适的位置，插入
            arr[j + 1] = current;
        }
    }

    // 希尔排序主函数
    public static void shellSort(int[] arr) {
        int n = arr.length;

        // 初始增量 gap，逐步缩小
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每组使用插入排序
            for (int i = gap; i < n; i++) {
                int current = arr[i];
                int j = i - gap;

                // 类似插入排序的“向左移动”，但跨度是 gap
                while (j >= 0 && arr[j] > current) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }

                arr[j + gap] = current; // 插入合适位置
            }
        }
    }

    // 打印数组工具函数
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 主函数：测试插入排序
    public static void main(String[] args) {
        int[] arr = {5, 2, 4, 6, 1, 3};
        System.out.println("排序前：");
        printArray(arr);

        shellSort(arr);

        System.out.println("排序后：");
        printArray(arr);
    }
}
